\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%
\usepackage{graphicx}
\usepackage{stfloats}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{listings}
\usepackage{color}
\usepackage{wrapfig}
\usepackage{mathtools}
 
\usepackage{algorithm}
\usepackage{algorithmic}


\lstloadlanguages{XML}


\newcommand{\beq}{\begin{equation}}
\newcommand{\enq}{\end{equation}}
\newcounter{mytempeqncnt}
\newcommand{\bquote}{\begin{quote}}
\newcommand{\equote}{\end{quote}}

\newcommand{\todo}[1]{\textcolor{red}{@TODO: #1}}
\newcommand{\dtr}[1]{\textbf{\textit{#1}$^\textbf{[dtr]}$}}

\begin{document}
\frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
% \addtocmark{Prior information and event spaces} % additional mark in the TOC

\title{Effective and Efficient Candidate Selection over Multiple Heterogeneous Datasets}

%
\titlerunning{}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
\author{Samur Araujo\inst{1}, Duc Thanh Tran\inst{2}, Arjen de Vries\inst{1}, Marcel Reinders\inst{1}}

% Jeffrey Dean \and David Grove \and Craig Chambers \and Kim~B.~Bruce \and
% Elsa Bertino}
% %
\authorrunning{}   % abbreviated author list (for running head)
 

\institute{Delft University of Technology, PO Box 5031, 2600 GA Delft, the Netherlands \email{{S.F.CardosodeAraujo}}
\and Karlsruher Institute of Technology, Germany \\
\email{ducthanh.tran@kit.edu}}

\maketitle
\begin{abstract} 
Establish high quality interlinking (owl:sameas) between different datasets is a challenge for the Linked Data. Current approaches tackle the problem of scalability in this process, focusing on finding candidate matches using a relatively simple but quick matching technique, which in a second phase are refined using a more expensive technique. In this paper, we tackle the effective and efficiency of the problem of \emph{candidate selection} over multiple heterogeneous datasets. We pose it as the problem of finding a query that retrieves a subset A of target instances that are possible matches for a source instance, \emph{such as A satisfied a minimization function F(A)}. We propose Sonda, a \emph{branch-and-bound based optimization framework} that can build candidate queries and evaluate the minimal set of queries that satisfy F(A). We intensively evaluate our approach on fourteen RDF datasets provide by two benchmarks. Our results shows that our framework achieve the best F1, towards Reduction Ratio (RR) and Pair Completeness (PC), in 96\% of the cases. 
 
\textbf{Keywords}: data integration, RDF interlinking, instance matching, candidate selection, query optimization.
\end{abstract} 

\input{sec-intro}
  
\input{sec-problem}
\input{sec-keyselection}
\input{sec-approach}
 
\input{sec-experiment}
\input{sec-related}

\section{Conclusion}
In this paper, we investigated the problem of candidate selection in the large and heterogeneous environment of the Web. We pose it as the problem of finding queries that retrieve candidate instances from the target dataset(s) for instances of a source dataset. These queries may vary in result quality and execution time. We propose Sonda, a branch-and-bound based optimization framework that finds time-efficient queries that select high quality results. We extensively evaluate Sonda and compare it against state-of-the-art approaches. The results show that Sonda achieves best F1 in 96\% of the cases. Also, we study time performance and show that this improvement in result quality does not necessarily come at the expense of efficiency: Sonda considers a large number of queries to achieves high recall but also, is able to choose more time-efficient queries to reduce the performance burden resulting from the large amount of queries. 


\bibliographystyle{abbrv}
\bibliography{iswc}
\end{document}
